Wyznaczanie planu sieci drogowej

Limit pamięci: 64 MB

Bajtazar wybiera się w podróż samochodową po Bajtocji, lecz niestety ma problemy z nabyciem mapy tego kraju. Od znajomych dowiedział się o pewnych właściwościach bajtockiej sieci dróg:

• W Bajtocji jest miast, ponumerowanych od do .
• Każda droga jest dwukierunkowa i łączy ze sobą pewne dwa różne miasta.
• Każde dwa różne miasta są połączone dokładnie jedną trasą, złożoną z jednej bądź większej liczby dróg, na której żadne miasto się nie powtarza.
• Najdłuższa z tras, na której żadne miasto się nie powtarza, składa się z dróg.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia liczby oraz ,
• wyznaczy dowolny plan sieci drogowej, zgodny z informacjami zdobytymi przez Bajtazara, lub stwierdzi, że żaden taki plan nie istnieje,
• wypisze wynik na standardowe wyjście.

Wejście

Pierwszy i jedyny wiersz wejścia zawiera dwie liczby całkowite oraz (, ), oddzielone pojedynczym odstępem.

Wyjście

Jeżeli nie istnieje żaden plan sieci drogowej, odpowiadający wartościom parametrów oraz , to pierwszy i jedyny wiersz wyjścia powinien zawierać jedno słowo BRAK. W przeciwnym przypadku wyjście powinno składać się z wierszy. Każdy wiersz powinien zawierać opis jednej dwukierunkowej drogi - dwie różne liczby całkowite z zakresu od do , oddzielone pojedynczym odstępem i oznaczające numery miast połączonych daną drogą. Kolejność wypisania dróg i numerów miast połączonych drogami może być dowolna.

Przykład

Dla danych wejściowych:

6 3

poprawną odpowiedzią jest:

1 3
2 3
3 4
4 5
4 6

Autor zadania: Jakub Radoszewski.